use std::cmp::Ordering;

/// A sorted array that maintains its elements in sorted order.
pub struct SortedArray<T> {
    data: Vec<T>,
    length: usize,
    _alloced: usize,
    equ_func: Box<dyn Fn(&T, &T) -> bool>,
    cmp_func: Box<dyn Fn(&T, &T) -> Ordering>,
}

impl<T> SortedArray<T> {
    /// Creates a new `SortedArray` with the specified initial capacity.
    ///
    /// # Arguments
    ///
    /// * `capacity` - The initial capacity of the array.
    /// * `equ_func` - A closure that determines if two values are equal.
    /// * `cmp_func` - A closure that determines the order of two values.
    ///
    /// # Returns
    ///
    /// A new `SortedArray` instance.
    pub fn new(
        capacity: usize,
        equ_func: Box<dyn Fn(&T, &T) -> bool>,
        cmp_func: Box<dyn Fn(&T, &T) -> Ordering>,
    ) -> Self {
        let capacity = if capacity == 0 { 16 } else { capacity };
        SortedArray {
            data: Vec::with_capacity(capacity),
            length: 0,
            _alloced: capacity,
            equ_func,
            cmp_func,
        }
    }

    /// Returns the element at the specified index.
    ///
    /// # Arguments
    ///
    /// * `index` - The index of the element to retrieve.
    ///
    /// # Returns
    ///
    /// A reference to the element at the specified index, or `None` if the index is out of bounds.
    pub fn get(&self, index: usize) -> Option<&T> {
        self.data.get(index)
    }

    /// Returns the length of the sorted array.
    ///
    /// # Returns
    ///
    /// The number of elements in the array.
    pub fn length(&self) -> usize {
        self.length
    }

    /// Inserts a new element into the sorted array while maintaining the sorted order.
    ///
    /// # Arguments
    ///
    /// * `data` - The element to insert.
    ///
    /// # Returns
    ///
    /// `true` if the insertion was successful, `false` otherwise.
    pub fn insert(&mut self, data: T) -> bool {
        let (left, right) = (0, self.length);
        let index = self.find_insert_index(data, left, right);

        if self.length + 1 > self._alloced {
            self.resize();
        }

        self.data.insert(index, data);
        self.length += 1;
        true
    }

    /// Removes the element at the specified index.
    ///
    /// # Arguments
    ///
    /// * `index` - The index of the element to remove.
    pub fn remove(&mut self, index: usize) {
        if index < self.length {
            self.data.remove(index);
            self.length -= 1;
        }
    }

    /// Removes a range of elements from the sorted array.
    ///
    /// # Arguments
    ///
    /// * `index` - The starting index of the range to remove.
    /// * `length` - The number of elements to remove.
    pub fn remove_range(&mut self, index: usize, length: usize) {
        if index + length <= self.length {
            self.data.drain(index..index + length);
            self.length -= length;
        }
    }

    /// Finds the index of the first occurrence of the specified element.
    ///
    /// # Arguments
    ///
    /// * `data` - The element to search for.
    ///
    /// # Returns
    ///
    /// The index of the element, or `None` if the element is not found.
    pub fn index_of(&self, data: &T) -> Option<usize> {
        let (left, right) = (0, self.length);
        let index = self.binary_search(data, left, right);
        if let Some(i) = index {
            if (self.equ_func)(data, &self.data[i]) {
                return Some(i);
            }
        }
        None
    }

    /// Clears the sorted array, removing all elements.
    pub fn clear(&mut self) {
        self.data.clear();
        self.length = 0;
    }

    fn find_insert_index(&self, data: T, left: usize, right: usize) -> usize {
        let mut left = left;
        let mut right = right;
        while left < right {
            let mid = (left + right) / 2;
            if (self.cmp_func)(&data, &self.data[mid]) == Ordering::Less {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        left
    }

    fn binary_search(&self, data: &T, left: usize, right: usize) -> Option<usize> {
        let mut left = left;
        let mut right = right;
        while left < right {
            let mid = (left + right) / 2;
            match (self.cmp_func)(data, &self.data[mid]) {
                Ordering::Less => right = mid,
                Ordering::Greater => left = mid + 1,
                Ordering::Equal => return Some(mid),
            }
        }
        None
    }

    fn resize(&mut self) {
        self._alloced *= 2;
        self.data.reserve(self._alloced);
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_insert_and_get() {
        let mut array = SortedArray::new(
            16,
            Box::new(|a: &i32, b: &i32| a == b),
            Box::new(|a: &i32, b: &i32| a.cmp(b)),
        );
        array.insert(5);
        array.insert(3);
        array.insert(8);
        assert_eq!(array.get(0), Some(&3));
        assert_eq!(array.get(1), Some(&5));
        assert_eq!(array.get(2), Some(&8));
    }

    #[test]
    fn test_remove() {
        let mut array = SortedArray::new(
            16,
            Box::new(|a: &i32, b: &i32| a == b),
            Box::new(|a: &i32, b: &i32| a.cmp(b)),
        );
        array.insert(5);
        array.insert(3);
        array.insert(8);
        array.remove(1);
        assert_eq!(array.get(0), Some(&3));
        assert_eq!(array.get(1), Some(&8));
    }

    #[test]
    fn test_index_of() {
        let mut array = SortedArray::new(
            16,
            Box::new(|a: &i32, b: &i32| a == b),
            Box::new(|a: &i32, b: &i32| a.cmp(b)),
        );
        array.insert(5);
        array.insert(3);
        array.insert(8);
        assert_eq!(array.index_of(&3), Some(0));
        assert_eq!(array.index_of(&5), Some(1));
        assert_eq!(array.index_of(&8), Some(2));
        assert_eq!(array.index_of(&10), None);
    }

    #[test]
    fn test_clear() {
        let mut array = SortedArray::new(
            16,
            Box::new(|a: &i32, b: &i32| a == b),
            Box::new(|a: &i32, b: &i32| a.cmp(b)),
        );
        array.insert(5);
        array.insert(3);
        array.insert(8);
        array.clear();
        assert_eq!(array.length(), 0);
    }
}
